星尘

454. 四数相加 II

发表于 更新于 分类于

454. 四数相加 II

题目

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
输入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

输出:
2

解释:
两个元组如下:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

题解

总体思路：

先用两个数组 nums1 和 nums2 的任意两个数进行相加得到的结果加入到 HashMap 集合的 Key 中，value 存放这个值的数量，然后让nums3 和 nums4 的任意两个数进行相加然后得到其相反数。再用 HashMap 集合中的 Key 和这个相反数进行匹配，若存在则记录下来。

这里 nums3 和 nums4 为什么要取它的相反值，因为 nums1和 nums2 已经得出和了，再求出 nums3 和 nums4 因为这四个值相加要等于0，所以对 nums3 和 nums4 的和一定是和 nums1 和nums2 的和相反的，再对 nums3 和 nums4 进行取反就得到了 nums1 和 nums2 的和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution:
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        # 四数之和只是在三数之和的基础上在增加一层循环
        result = []

        # 特判，对于数组长度 n，如果数组为 null 或者数组长度小于 4，返回 []
        if len(nums) < 4:
            return []

        size = len(nums)
        nums.sort()

        for i, v in enumerate(nums):
            # 判断当前值是否和上一位值是否重复，重复的就跳过，目的是为了去除重复解
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            for k in range(i + 1, size):
                if k > i + 1 and nums[k] == nums[k - 1]:
                    continue

                left = k + 1
                right = size - 1

                # 只要左指针没有超过右指针，那么就一直循环
                while left < right:
                    sum_value = v + nums[left] + nums[right] + nums[k]
                    if sum_value > target:
                        # 和值大于 target, 右指针需要左移
                        right -= 1
                    elif sum_value < target:
                        # 和值小于 target, 左指针需要右移
                        left += 1
                    else:
                        result.append([v, nums[left], nums[right], nums[k]])
                        # 判断左边界和右边界是否和下一位值重复，目的是为了去除重复解
                        while left != right and nums[left] == nums[left + 1]:
                            left += 1
                        while left != right and nums[right] == nums[right - 1]:
                            right -= 1
                        # 最后左右指针各移动一步
                        right -= 1
                        left += 1
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
func fourSum(nums []int, target int) [][]int {
	var result [][]int

	if len(nums) < 4{
		return result
	}

	size := len(nums)
	sort.Ints(nums)

	for i, v:= range nums{
		if i > 0 && nums[i] == nums[i-1]{
			continue
		}

		for k := i + 1; k < size; k++ {
			if k > i+1 && nums[k] == nums[k-1] {
				continue
			}

			left := k +1
			right := size - 1

			for left < right{
				sumValue := v + nums[left] + nums[right] + nums[k]
				if sumValue > target{
					right -=1
				}else if sumValue < target {
					left += 1
				}else{
					result = append(result, []int{v, nums[left], nums[right], nums[k]})

					for left != right && nums[left] == nums[left+1]{
						left += 1
					}
					for left != right && nums[right] == nums[right-1]{
						right -=1
					}
					left +=1
					right -=1
				}
			}
		}
	}
	return result
}

变体

总结

参考